package DynamicProgramming;

import org.junit.Test;

import java.util.ArrayList;
import java.util.List;

public class _689_MaximumSumof3Non_OverlappingSubarrays {

    @Test
    public void test() {
        int[] nums = new int[]{1, 2, 1, 2, 6, 7, 5, 1};
        int k = 2;
        maxSumOfThreeSubarrays_w(nums, k);
    }

    public static int[] maxSumOfThreeSubarrays_w(int[] nums, int k) {
        int[] res = new int[3];
        int len = nums.length - k + 1;
        int[] sums = new int[len];
        int[] dp = new int[len];
        //simplify the calculation
        int sum = 0;
        //resultList
        List<List<Integer>> lists = new ArrayList<>();
        int max = Integer.MIN_VALUE;
        int pos = 0;
        for (int i = 0; i < k; i++) {
            sum += nums[i];
        }
        dp[0] = sums[0] = sum;
        lists.add(new ArrayList<>());
        lists.get(0).add(0);
        for (int i = 1; i < len; i++) {
            lists.add(new ArrayList<>());
            lists.get(i).add(i);
            sums[i] = sums[i - 1] - nums[i - 1] + nums[i + k - 1];
            dp[i] = sums[i];
        }

        for (int i = k; i < len; i++) {
            int tempPos = 0;
            for (int j = i - k; j >= 0; j--) {
                if (dp[i] <= (sums[i] + dp[j]) && (lists.get(i).size() + lists.get(j).size() <= 3)) {
                    dp[i] = sums[i] + dp[j];
                    tempPos = j;
                    if (dp[i] >= max) {
                        max = dp[i];
                        pos = i;
                    }
                }
            }
            lists.get(i).addAll(lists.get(tempPos));
        }
        return new int[]{lists.get(pos).get(2), lists.get(pos).get(1), lists.get(pos).get(0)};
    }

    public int[] maxSumOfThreeSubarrays(int[] nums, int K) {
        //W is an array of sums of windows
        int[] W = new int[nums.length - K + 1];
        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            if (i >= K) sum -= nums[i-K];
            if (i >= K-1) W[i-K+1] = sum;
        }

        int[] left = new int[W.length];
        int best = 0;
        for (int i = 0; i < W.length; i++) {
            if (W[i] > W[best]) best = i;
            left[i] = best;
        }

        int[] right = new int[W.length];
        best = W.length - 1;
        for (int i = W.length - 1; i >= 0; i--) {
            if (W[i] >= W[best]) best = i;
            right[i] = best;
        }

        int[] ans = new int[]{-1, -1, -1};
        for (int j = K; j < W.length - K; j++) {
            int i = left[j - K], k = right[j + K];
            if (ans[0] == -1 || W[i] + W[j] + W[k] >
                    W[ans[0]] + W[ans[1]] + W[ans[2]]) {

                ans[0] = i;
                ans[1] = j;
                ans[2] = k;
            }
        }
        return ans;
    }
}
